import collections
from typing import List


class Permutation:
    def __init__(self, mod=10 ** 9 + 7):
        self._mod = mod
        self._size = 0

        self._factorial = [1]  # 阶乘缓存列表 : self.fact[i] = i!
        self._factorial_inv = [1]  # 阶乘的乘法逆元缓存列表

    def factorial(self, n):
        """计算阶乘"""
        if n > self._size:
            for i in range(self._size + 1, n + 1):
                self._factorial.append((self._factorial[-1] * i) % self._mod)
                self._factorial_inv.append(pow(self._factorial[-1], self._mod - 2, self._mod))
            self._size = n
        return self._factorial[n]

    def arrange(self, n, m):
        """排列数公式"""
        return self.factorial(n) // self.factorial(n - m)

    def comb(self, n, m):
        """组合数公式"""
        return self.arrange(n, m) // self.factorial(m)


permutation = Permutation()


class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        size = len(nums)

        # 处理重复的情况
        times = 1
        for k, v in collections.Counter(nums).items():
            times *= permutation.factorial(v)

        # 处理相互之间的链接关系
        stat = [[False] * size for _ in range(size)]
        for i in range(size):
            for j in range(size):
                v = nums[i] + nums[j]
                if pow(v, 0.5).is_integer():
                    stat[i][j] = stat[j][i] = True

        # 定义状态矩阵：dp[i][j] = 当前位于i顶点，当前遍历状态为j时候的步骤数
        dp = [[0] * pow(2, size) for _ in range(size)]

        # 基于广度优先搜索的状态转移
        queue1 = set()
        for i in range(size):
            dp[i][1 << i] = 1
            queue1.add((i, 1 << i))

        while queue1:
            queue2 = set()
            for i, stat1 in queue1:
                for j in range(size):
                    if not (1 << j) & stat1 and stat[i][j] is True:
                        stat2 = (1 << j) | stat1
                        dp[j][stat2] += dp[i][stat1]
                        queue2.add((j, stat2))
            queue1 = queue2

        ans = sum(dp[i][-1] for i in range(size))
        return ans // times


if __name__ == "__main__":
    print(Solution().numSquarefulPerms([1, 17, 8]))  # 2
    print(Solution().numSquarefulPerms([2, 2, 2]))  # 1
